money, things = map(int, input().split())
# from pprint import pprint

# money, things = 50,5
money = money // 10  # money都是10的整数，整除后，减小循环次数
# 三列分别表示主件，附件1，附件2
weight = [[0] * 3 for _ in range(0, things + 1)]  # 价格
value = [[0] * 3 for _ in range(0, things + 1)]  # 价值=价格*重要度
result = [[0] * (money + 1) for _ in range(0, things + 1)]
# input_str = [
#     (0,0,0),
#     (20, 3, 5),
#     (20, 3, 5),
#     (10, 3, 0),
#     (10, 2, 0),
#     (10, 1, 0),
# ]
for i in range(1, things + 1):
    prices, degree, depend = map(int, input().split())  # 分别为价格，重要性，主附件
    # prices, degree, depend =input_str[i]  # 分别为价格，重要性，主附件
    prices = prices // 10

    if depend == 0:  # 主件
        weight[i][0] = prices
        value[i][0] = prices * degree

    elif weight[depend][1] == 0:  # 附件
        weight[depend][1] = prices  # 第一个附件
        value[depend][1] = prices * degree

    else:
        weight[depend][2] = prices  # 第二个附件
        value[depend][2] = prices * degree

for i in range(1, things + 1):
    for j in range(1, money + 1):
        if j>= weight[i][0]:
            # 先算主件
            result[i][j] = max(result[i-1][j], result[i-1][j- weight[i][0]] + value[i][0])
            # 计算主件后，计算附件1
            if j >= (weight[i][0] + weight[i][1]):
                result[i][j] = max(result[i][j], result[i-1][j- weight[i][0]- weight[i][1]] + value[i][0] + value[i][1])
            # 计算主件后，计算附件2
            # 附件1的结果叠加在result[i][j]里
            if j>=(weight[i][0] + weight[i][2]):
                # -> 计算附件2是跟前面叠加的结果取最大值
                result[i][j] = max(result[i][j], result[i-1][j- weight[i][0]- weight[i][2]] + value[i][0] + value[i][2])
                # 如果两个附件的价格也能购买
                if j >= (weight[i][0] + weight[i][1] + weight[i][2]):
                    result[i][j] = max(result[i][j], result[i - 1][j - weight[i][0] - weight[i][1]- weight[i][2]] + value[i][0] + value[i][1]+ value[i][2])
        else:
            result[i][j] = result[i-1][j]

print(result[things][money]*10)